# -*- coding:utf-8 -*-
class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 1:
            return 0
        res = [1]
        t2 = t3 = t5 = 0
        nextIdx = 1
        while nextIdx < index:
            minNum = min(res[t2]*2,res[t3]*3,res[t5]*5)
            res.append(minNum)
            while res[t2] * 2 <= minNum:
                t2 += 1
            while res[t3] * 3 <= minNum:
                t3 += 1
            while res[t5] * 5 <= minNum:
                t5 += 1
            nextIdx += 1
        return res[nextIdx - 1]

    '''
    要注意，后面的丑数是有前一个丑数乘以2，3，5中的一个得来。因此可以用动态规划去解
    '''